# https://zhuanlan.zhihu.com/p/145536254?utm_source=wechat_session&utm_medium=social&utm_oi=934568061286092800&utm_campaign=shareopn
class KMPIndex(object):
    def __init__(self, value: str):
        self.value = value
        # 建立next数组
        _next = [0]
        for i in range(1, len(value)):
            # 求某个字串, 前k个和后k个相等时最大的k
            cmp = value[:(i + 1)]
            k = i + 1
            while k >= 1:
                k -= 1
                if cmp[:k] == cmp[-k:]:
                    break
            _next.append(k)
        self.next = _next

    def index(self, string: str) -> int:
        # string[i]和value[j]比较:
        # if 相等: i+=1, j+=1
        # if 不相等:
        #         if j=0: i + 1
        #         else: j = next[j - 1]
        # 重复上述步骤直到i >= len(string)或j>=len(value)
        i, j = 0, 0
        while i < len(string) and j < len(self.value):
            if string[i] == self.value[j]:
                i += 1
                j += 1
            else:
                if j == 0:
                    i += 1
                else:
                    j = self.next[j - 1]
        return i - j if j == len(self.value) else -1


print(KMPIndex('ABAABAC').index('ABABAABAABAC'))
